This disclosure relates to computer graphics. More specifically, the disclosure relates to techniques for providing temporally coherent deformations of objects, such as hair.
The motions of secondary elements in computer graphics imagery such as hair or cloth are often too complex for an animator to directly control. Instead of a human animator determining the motion of these secondary elements, some computer programs use physically-based numerical methods and techniques to simulate their motion over time. For hair, this is sometimes accomplished by modeling the physical properties of the hair (e.g., how the hair reacts due to forces or collisions with solid objects, how the hair deforms or collides with itself, or the like), the external forces on the hair (gravity, wind), the motions of kinematic or reference elements (e.g., the characters or objects upon which the hair is placed), or the like.
In many cases, the animation of kinematic or reference elements is specified and is independent of and/or unaffected by the motion of the dynamic elements (e.g., the hair). As a concrete example, consider an animation of a character, having several hundreds of thousands, to millions of strands of hair or fur upon the character. In various embodiments, the character (the kinematic or reference element) is directly animated by a skilled human animator. However, the motion of the hair (the dynamic element), in response to the character's animation, is simulated by a computer simulation program using physically-based numerical techniques.
If the physical properties and external forces acting on the dynamic elements are accurately modeled, the resulting motion is often “plausible” and seemingly realistic to a viewer. In other words, it will appear to a viewer that the hair hangs down naturally, and that the hair reacts naturally in response to the character's motions. The process of determining the motion of hair or fur over time in reaction to an object's movement (e.g., a character's movements) is called herein a “simulation process,” while the software/computer hardware that performs the process is called herein a “simulation system.” Typically, the software and mathematics underlying physical simulations of this nature are highly complex.
It has been determined by the inventors, that for any number of reasons, a simulation system may produce output motion that typically is mostly, but not completely, correct with regard to interpenetrations between the hair and other objects or reference elements. A challenge is to ensure that at every frame, the position of the hairs avoids interpenetrations. One way to do this is to change the geometry of the hair to avoid the interpenetrations, e.g., bend or otherwise deform the hair around objects, rather than simply passing through them. For large magnitude deformations, it is extremely important that the displacement vary smoothly from frame to frame of the animation, or one quite easily sees hair that jumps about, in a seemingly random fashion. In other words, hair deformations must be temporally coherent.
One way to introduce coherence is by maintaining history of a hair's deformation. For example, if a hair's deformation (if any) is known at a previous point in time, and a small step is taken forward in time (e.g., small enough so that movement of a reference object is small), then the hair does not require a deformation very far from its last state to remove interpenetrations. Using “history” (i.e., the known previous state) in this manner allows one to use any number of simulation-based techniques that guarantee a temporally coherent outcome.
However, using history adds a serious restriction because it requires one to compute the deformations of the hair in sequential time-wise order. In particular, the deformation of the hairs at some frame N cannot be determined without first determining its deformation at frame N−1, and so on. This may not seem a serious restriction, since the process of physically simulating hair itself may already has this dependence on history. (The simulation system must compute the motion of the hair at frame 1, then frame 2, etc.) However, hair simulation systems typically simulate the motion of only a very small number of hairs (for example, some few thousands). In contrast, a rendering program can extrapolate the geometry of “millions” of hair, based upon those few thousands of hairs computed by the simulation system, and may draw all those millions of hairs in the final output image. Yet all of those millions of hairs, at each frame of the animation, may need to be free of interpenetrations.
If the deformation state of these millions of hairs at any frame is made to depend upon the deformation state at the previous frame, then the rendering process must render frames in time-wise order, from first to last, maintaining a history of each hair's deformation state over time. This is an unacceptable requirement because today's production environments depend on being able to distribute the rendering of a sequence of frames over many computers. For example, in a one hundred frame sequence of animation, it is typical for each of those one hundred frames to be rendered by a separate computer at the same time. Doing so requires that the computations for each frame be independent of all other frames. However, by requiring that the deformation of a hair at frame n depend upon its deformation at frame n−1, we require that the frames be computed sequentially, rather than in parallel. However, requiring that the deformation of a hair at frame n+1 depend upon its deformation at frame n, in turn requires that the frames be computed sequentially, rather than in parallel.
Accordingly, what is desired are improved methods and apparatus for solving the problems discussed above. Additionally, what is desired are improved methods and apparatus for reducing some of the drawbacks discussed above.